// 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
//
// 说明：每次只能向下或者向右移动一步。
//
//  
//
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/minimum-path-sum
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const h = grid.length
  const w = grid[0].length
  const dp = new Array(h).fill(0).map(() => new Array(w).fill(0))
  let total = 0
  for (let i = 0; i < w; i++) {
    total += grid[0][i]
    dp[0][i] = total
  }
  total = 0
  for (let i = 0; i < h; i++) {
    total += grid[i][0]
    dp[i][0] = total
  }

  for (let i = 1; i < h; i++) {
    for (let j = 1; j < w; j++) {
      const p1 = dp[i][j - 1]
      const p2 = dp[i - 1][j]
      dp[i][j] = Math.min(p1, p2) + grid[i][j]
    }
  }

  return dp[h - 1][w - 1]

  // 1. 0,0 到 x,y 的最短路径长度
  const helper = (x, y) => {
    // 4. base case
    // helper(0, i)
    // helper(i, 0)
    if (x === 0) {
      let total = 0
      for (let i = 0; i <= y; ++i) {
        total += grid[0][i]
      }
      return total
    }
    if (y === 0) {
      let total = 0
      for (let i = 0; i <= x; ++i) {
        total += grid[i][0]
      }
      return total
    }

    // 3. helper(x, y) = min(helper(i, j))
    // i = x, x - 1
    // j = y, y - 1
    const p1 = helper(x, y - 1)
    const p2 = helper(x - 1, y)

    return Math.min(p1, p2) + grid[x][y]
  }
  // 2. x 从 0 到 grid.length - 1, y 从 0 到 grid[0].length - 1
  const res = helper(grid.length - 1, grid[0].length - 1)

  return res
}

console.log(
  minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
)